#include <stdio.h>
#include <malloc.h>
#include"..\Stack\zyf_Stack.h"
#define ERROR 2
#define OK 1
#define MAX_SIZE 100
typedef int Status;

/*
	递归多项式数列，用非递归的方式计算
	当n=0  Pn = 1
	当n=1  Pn = 2x
	当n>1  Pn = 2x Pn-1 -2(n - 1)Pn-2
*/
Status calculate(int n,int x,int *e)
{//n为项数,x为自变量,e为接受最后计算的函数值
	int val,j,k;
	j = 0;
	k = 0;
	SqStack S;
	Init_Stack(&S);

	if (n < 0)
		return ERROR;

	if (n == 0)
	{
		*e = 1;
		printf("-----%d\n", *e);
		return OK;
	}
	else if (n == 1)
	{
		*e = x*2;
		return OK;
	}
	else if(n > 1)
	{
		//printf("------%d\n",x*2);
		push(&S,1);
		push(&S,x*2);//前两项入栈

		for (int i = 1;i < n;i++)
		{
			pop(&S,&j);
			printf("----%d\n",j);
			pop(&S,&k);
			printf("-----%d\n",k);
			val = 2*x*j - 2*i*k;//计算递归表达式
			push(&S,val);
		}

		pop(&S,e);
	}

	return OK;
}

double calculate1(int n, double x)
{	
	struct stack
	{
		double val;	
	}st[MAX_SIZE];

	int top = 0;
	double p,q,tempval;

	if (n == 0)
		return 1;
	else if (n == 1)
		return 2*x;
	else if (n > 1)
	{
		st[top++].val = 1;
		st[top++].val = 2*x;
		printf("---%d---%lf\n",top,st[1].val);
		for(int i = 2;i <= n;i++)
		{
			q = st[--top].val;
			//printf("---%lf\n",q);
			p = st[--top].val;
			tempval = 2*x*q-2*(i-1)*p;
			p = q;
			q = tempval;
			p = st[top++].val;
			q = st[top++].val;
		}
	}

	return st[--top].val;
}

int main(void)
{
	
	double s;

	s = calculate1(2,1.0);
	printf("---%lf\n",s);
	//printf("状态码：%d\n计算结果是%d\n",s,e);
	


}	